package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Vector;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

import cern.colt.Sorting;
import cern.colt.function.IntComparator;

import com.yahoo.labs.snow.ProblemInstance;
import com.yahoo.labs.snow.Snowflake;

/**
 * A general method for finding snowflakes.
 * 
 * @author chato
 *
 */
public abstract class Solver {
	
	static Logger logger = Logger.getLogger(Solver.class);
	
	static {
		BasicConfigurator.resetConfiguration();
		BasicConfigurator.configure();
	}
	
	/**
	 * The problem instance that needs to be solved.
	 */
	ProblemInstance problem = null;
	
	public Solver(ProblemInstance problem) {
		this.problem = problem;
	}
	
	/**
	 * Finds a set of snowflakes.
	 * 
	 * @param numSnowflakes the number of snowflakes returned
	 * @return a set of snowflakes
	 */
	public abstract Vector<Snowflake> solve(int numSnowflakes);
	
	/**
	 * Returns true iff "currentSnowflake UNION node": (1) is within budget and (2) honors coverage constraint.
	 * 
	 * @param currentSnowflake current members of snowflake
	 * @param node node to add
	 * @return true iff the union would be a valid snowflake
	 */
	boolean checkBudgetAndCoverageConstraint(IntOpenHashSet currentSnowflake, int node) {
		return checkBudgetConstraint(currentSnowflake, node) && checkCoverageConstraint(currentSnowflake, node);
	}
	
	boolean checkBudgetAndCoverageConstraint(IntOpenHashSet snowflake1, IntOpenHashSet snowflake2) {
		return checkBudgetConstraint(snowflake1, snowflake2) && checkCoverageConstraint(snowflake1, snowflake2);
	}
	
	boolean checkBudgetConstraint(IntOpenHashSet currentSnowflake, int newNode) {
		int currentCost = 0;
		for( int node: currentSnowflake ) {
			currentCost += problem.getCost(node);
		}
		if( currentCost + problem.getCost(newNode) <= problem.getBudget() ) {
			// Within budget
			return true;
		} else {
			// Exceeds budget
			return false;
		}
	}
	
	boolean checkBudgetConstraint(IntOpenHashSet snowflake1, IntOpenHashSet snowflake2) {
		int currentCost = 0;
		for( int node: snowflake1 ) {
			currentCost += problem.getCost(node);
			if( currentCost > problem.getBudget() ) {
				return false;
			}
		}
		for( int node: snowflake2 ) {
			currentCost += problem.getCost(node);
			if( currentCost > problem.getBudget() ) {
				return false;
			}
		}
		return true;
		
	}

	boolean checkCoverageConstraint(IntOpenHashSet currentSnowflake, int newNode) {
		IntOpenHashSet coverageCovered = new IntOpenHashSet();
		for( int node: currentSnowflake ) {
			IntOpenHashSet covers = problem.getCover(node);
			if( covers == null ) {
				throw new IllegalStateException( "Node " + node + " does not cover anything");
			}
			for( int cover: covers ) {
				if( coverageCovered.contains(cover) ) {
					// currentSnowflake is not valid
					return false;
				}
				coverageCovered.add(cover);
			}
		}
		for( int cover: problem.getCover(newNode) ) {
			if( coverageCovered.contains(cover) ) {
				// adding this newNode is not valid
				return false;
			}
			coverageCovered.add(cover);
		}
		
		// It is OK to add the newNode
		return true;
	}
	
	boolean checkCoverageConstraint(IntOpenHashSet snowflake1, IntOpenHashSet snowflake2) {
		IntOpenHashSet coverageCovered = new IntOpenHashSet();
		for( int node: snowflake1 ) {
			IntOpenHashSet covers = problem.getCover(node);
			if( covers == null ) {
				throw new IllegalStateException( "Node " + node + " does not cover anything");
			}
			for( int cover: covers ) {
				if( coverageCovered.contains(cover) ) {
					return false;
				}
				coverageCovered.add(cover);
			}
		}
		
		for( int node: snowflake2 ) {
			IntOpenHashSet covers = problem.getCover(node);
			if( covers == null ) {
				throw new IllegalStateException( "Node " + node + " does not cover anything");
			}
			for( int cover: covers ) {
				if( coverageCovered.contains(cover) ) {
					return false;
				}
				coverageCovered.add(cover);
			}
		}
		
		// It is OK to add the newNode
		return true;
	}
	
	Snowflake pickFlakeGivenPermutation(final int pivot, int[] clusterMembersPermuted) {
		IntOpenHashSet picked = new IntOpenHashSet();
		picked.add(pivot);

		for (int newMember : clusterMembersPermuted) {
			if (checkBudgetAndCoverageConstraint(picked, newMember)) {
				picked.add(newMember);
			}
		}
		return new Snowflake(picked, problem);
	}
	
	/**
	 * Builds a good snowflake with an element at its center.
	 * 
	 * @param pivot central element
	 * @param clusterMembers possible other elements in the cluster
	 * @return a good snowflake containing the central element
	 */
	Snowflake pickFlake(final int pivot, IntOpenHashSet clusterMembers) {
		
		// Sort clusterMembers by decreasing compatibility
		int[] membersSorted = clusterMembers.toArray(new int[] {});

		Sorting.quickSort(membersSorted, 0, membersSorted.length, new IntComparator() {

			@Override
			public int compare(int o1, int o2) {
				return (int) Math.signum(problem.getCompat(pivot, o2) - problem.getCompat(pivot, o1));
			}
		});

		return pickFlakeGivenPermutation(pivot, membersSorted);
	}
}
